/**
 * 给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
 * 实例:
 * 输入：candidates = [2,3,6,7], target = 7,
 *       所求解集为：
 *   [
 *     [7]
 *     [2,2,3]
 *   ]
 */


 /**
 * @param {number[]} candidates
 * @param {number} target
 * @return {number[][]}
 */
var combinationSum = function(candidates, target) {
    let result = []
    for(let i = 0; i< candidates.length; i++){
        if(candidates[i] === target){
            result.push([candidates[i]])
            continue
        }
        for(let j = 0; j< candidates.length -i -1; j++){
            if(candidates[i] + candidates[j] == target) {
                result.push([i,j])
            }
        }
    } 
    // 这里每组结果会生成两个, 所以选取前一半就可以了.
    console.log(result);
    return result.slice(0, Math.floor(result.length/2));
};

let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 , 11, 12, 13]
let target = 9
combinationSum(arr, target)




var combinationSum1 = function(nums, target) {
    const bt = (res, curRes, curSum, index) => {
        if (curSum === target) {
            res.push(curRes.slice());
            return;
        }
        if (curSum > target) return;

        for (let i = index; i < nums.length; i++) {
            if (curSum < target) {
                curRes.push(nums[i]);
                bt(res, curRes, curSum+nums[i], i); // 这里是关键，每次从 i 开始
                curRes.pop();
            } else {
                break;
            }
        }
    }

    let res = [];
    bt(res, [], 0, 0);
    return res;
};
